KNN - ideia

• Relembrando: \(Y = r(\mathbf{X}) + \varepsilon\)
  • A relação sistemática entre \(\mathbf{X}\) e \(Y\) é “bem comportada”: \(\mathbf{X}\)’s próximos \(\Rightarrow\) \(Y\)’s semelhantes
• Usar essa ideia para criar um estimador \(g\)
• “Diga-me com quem andas e te direi quem és”

KNN - formalização

\[g(\mathbf{x}) = \frac{1}{k}\sum_{i \in \mathcal{N}_{\mathbf{x}}^{(k)}} y_i,\] onde \(\mathcal{N}_{\mathbf{x}}^{(k)}\) é o conjunto dos índices das \(k\) observações mais próximas de \(\mathbf{x}\), ou seja, \[\mathcal{N}_{\mathbf{x}}^{(k)} = \left\{i \in \{1, \dots, n\} ~ \left| ~ d(\mathbf{x}_i, \mathbf{x}) \leq d_{\mathbf{x}}^k \right\}\right.,\] e \(d_{\mathbf{x}}^k\) representa a distância do \(k\)-ésimo vizinho mais próximo de \(\mathbf{x}\) para \(\mathbf{x}\).

KNN - propriedades

• Hiperparâmetro \(k\) \(\Rightarrow\) validação cruzada
• \(k\) alto \(\Rightarrow\) modelo simples
  • \(k \to \infty\) \(\Rightarrow\) \(g\) constante
  • Viés alto, baixa variância
• \(k\) pequeno \(\Rightarrow\) modelo mais complexo
  • Variância alta, viés baixo
  • Requer mais dados para ser mais fidedigno
  • Quão mais? Veremos mais adiante!

KNN - Exemplo

KNN - Exemplo

scikit-learn - KNeighborRegressor

KNN = KNeighborsRegressor(n_neighbors = 1)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)

Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 5)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)

Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 50)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)

Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 150)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)

Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

Encontrando o melhor \(k\) por validação cruzada

KNN = KNeighborsRegressor()
param_grid_KNN = {"n_neighbors": range(1, 31)}
KNNCV = GridSearchCV(KNN, param_grid = param_grid_KNN,
                     scoring='neg_mean_squared_error', cv = 5)
KNNCV.fit(x_tr.reshape(-1, 1), y_tr)
print(KNNCV.best_estimator_)

KNeighborsRegressor(n_neighbors=17)

KNN - Exemplo

Otimizando outros hiperparâmetros por validação cruzada

KNN = KNeighborsRegressor()
param_grid_KNN = {"n_neighbors": range(1, 31),
                  "weights": ['uniform', 'distance'], "p": range(1, 5)}
KNNCV = GridSearchCV(KNN, param_grid = param_grid_KNN, scoring='neg_mean_squared_error', cv = 5)
KNNCV.fit(x_tr.reshape(-1, 1), y_tr)
print(KNNCV.best_estimator_, "Weights: ", KNNCV.best_estimator_.weights)

KNeighborsRegressor(n_neighbors=17, p=1) Weights:  uniform

KNN - Observações

• Jogamos algumas coisas pra baixo do tapete!
  • algorithm
  • leaf_size
• “See Nearest Neighbors in the online documentation for a discussion of the choice of algorithm and leaf_size.”

A maldição da dimensionalidade 👻

A maldição da dimensionalidade

“Being able to sense simultaneously thousands of variables on each ”individual” sounds like good news: Potentially we will be able to scan every variable that may influence the phenomenon under study. The statistical reality unfortunately clashes with this optimistic statement: Separating the signal from the noise is in general almost impossible in high-dimensional data. This phenomenon […] is often called the ‘curse of dimensionality’.”

A maldição da dimensionalidade

“The impact of high dimensionality on statistics is multiple. First, high-dimensional spaces are vast and data points are isolated in their immensity. Second, the accumulation of small fluctuations in many different directions can produce a large global fluctuation. Third, an event that is an accumulation of rare events may not be rare. Finally, numerical computations and optimizations in high-dimensional spaces can be overly intensive.”

Fonte: Christophe Giraud - Introduction to High-Dimensional Statistics

Distâncias em alta dimensão

• Conjunto de \(n\) observações
• Cada observação é um vetor de \(p\) atributos
  • Cada entrada uniformemente distribuída em \((0, 1)\)
• Chamaremos tal conjunto de dados de \(\mathbf{X}\)
• Consideremos os cenários \(n \approx p\) ou mesmo \(n < p\)
• Calcular distâncias entre pares distintos de observações
  • Linhas da matriz \(\mathbf{X}\)
• Agradecimento: Códigos de Lucas Galdino (Projetos 01 e 02 da edição de 2022/02 dessa disciplina)

O que está acontecendo?

• \(p\) cresce \(\Rightarrow\) gráficos com o mesmo “formato” e se “deslocando” para a direita
• Possíveis hipóteses:
  • O desvio padrão é constante à medida que \(p\) cresce
  • A média cresce à medida que \(p\) cresce
• Vamos verificá-las!

Uma definição preliminar

• Definição: Dada uma variável aleatória \(X\) com média diferente de zero, definimos o seu coeficiente de variação como \[\mathrm{cv}(X) = \frac{\sqrt{\mathbb{V}(X)}}{\mathbb{E}[X]}.\]

Interpretando a tabela

• \(p\) cresce \(\Rightarrow\) o coeficiente de variação é cada vez mais próximo de zero
• Possível conclusão: quando \(p\to \infty\), temos que \(\mathrm{cv} \to 0\)
• Mas como se dá essa convergência?

Interpretando a nova tabela

• Desvio padrão parece estabilizar-se (ou crescer muito devagar)
• A média parece crescer
• Verifiquemos isso rigorosamente!
• \(\mathbf{X}^{(i)}\) e \(\mathbf{X}^{(j)}\) duas linhas distintas da matriz \(\mathbf{X}\): \[\frac{\sqrt{\mathbb{V}\left(\left\|\mathbf{X}^{(i)} - \mathbf{X}^{(j)}\right\|^2\right)}}{\mathbb{E}\left[\left\|\mathbf{X}^{(i)} - \mathbf{X}^{(j)}\right\|^2\right]} \propto \frac{1}{\sqrt{p}}.\]

O que isso tem a ver com o KNN?

• KNN é baseado em distâncias
• Em alta dimensão, a noção de “distância” é curiosa!
• Pontos mais “espaçados” entre si
• Possível perda de capacidade preditiva do KNN

Um pequeno experimento

• \(\mathbf{X}\) matriz \(n \times p\), com \(p \gg n\)
• Entradas uniformes em \((0, 1)\)
• Fixar a primeira linha de \(\mathbf{X}\)
• Calcular a proporção da menor distância para outro vetor linha de \(\mathbf{X}\) pela média da distâncias para todos os outros vetores linha de \(\mathbf{X}\)

Conclusão para o KNN

• \(p \to \infty\) \(\Rightarrow\) proporção tende a 1
• À medida que \(p\) cresce, a menor distância e a distância média são cada vez mais similares
• A noção de \(K\) vizinhos mais próximos perde sentido!